Processing speed can be dramatically improved by paralleling and vectorizing a process for elements of a multidimensional array. In particular, in a processor with multiple execution units such as IA64 or PowerPC, an effect of improved processing speed by such optimizations is remarkable. In order to perform such optimizations, it is necessary to analyze dependency among processes of multidimensional array elements and locations of array elements. However, in a language like Java which implements a multidimensional array by means of an array of array objects, it is difficult to perform such analyses since element configuration of a multidimensional array may change at an execution time.
Conventionally, there were roughly two solutions to this problem. First, there is a known method of performing an analysis by scanning addresses of multidimensional array elements accessed by a certain process at an execution time. There is also a known method of implementing a multidimensional array without any change in element configuration at an execution time by means of extension of language specifications or installation of a unique library. It certainly becomes possible to optimize a process for a multidimensional array by using these methods. However, there were following various problems in these methods.
First, as to the former method, in addition to taking too much time for scanning addresses, there was a problem of having to stop a garbage collector from the time the address scanning is started until processing of an array ends. In particular, the problem of the time for address scanning is fatal for Java in which processing by Just-in-Time compiler is becoming general, so it is not a realistic solution.
On the other hand, as to the latter method, it is proposed by Sun Microsystems Inc. to use a class to access, as a multidimensional array, an area to which memory is allocated as a one-dimensional array. It first provides a class as follows.
final class FloatMatrix2D {private final float m;private final int cols;public FloatMatrix2D(int c, int r){cols=c;m=new float c*r ;}public float get(int c, int r){return m cols*r+c ;}}
Here, it is a method wherein, by using method in-lining and operator overloading, an expression described as,
FloatMatrix2D f=new FloatMatrix2D(cols, rows)fil,j1 =fi2,j2 +4;is handled as follows,fi1,j1 =fi2,j2 +4;—T=f.get(i2,j2)+4;f.put(i1,j1,T);—T=f cols*j2+i2 +4;fcols*j1+i1 =T;By using such a method, it is possible to directly access elements without undergoing reference to any object array. In addition, it is not necessary to check an index as required when referring to an object array. In this method, however, there is a problem that application of an analysis required for parallelization or optimization becomes difficult.
Namely, in the above method, as there is no information in the source rendered into bytecode, it is not possible to perform any more analysis of dependency among array accesses than an analysis in an index converted to one dimension. Accordingly, it becomes very difficult to detect parallelism taking multidimensionality into consideration, so application of parallelization cannot be expected in many cases.
For instance,
for jfor ifi,j =f2*i−1,j ;in a program as above, since it can easily be analyzed as having no dependency in the direction of j, great parallelism can be obtained by skewing the innermost loop in the direction of j or unrolling the loop in the direction of j. However, if the bytecode is converted to f cols*j+i=f cols*j+2*i−1 it becomes necessary to seek if there is an integer solution in cols*j1+i1=cols*j2+2*i2−1and decide whether there is any dependency as to the direction of j. This means that a simple analytic problem has become an NP complete problem. Also in general, it is thinkable that a problem becomes more difficult to solve if multidimensional information reduces to one dimension, and thus the method of Sun Microsystems Inc. is not a method suited to dependency analysis for parallelization.
There is also another method to allow dependency analysis by modifying or extending language specifications. For instance, a method as in Fortran wherein a multidimensional array is introduced to a language is thinkable. Or even in the above-mentioned method wherein an array is simply one-dimensionalized, dependency analysis should be made possible by adding extended specifications as follows. Namely, in the following expression used in the preceding example,
f cols*j+i=f cols*j+2*i−1
if language specifications are extended so that a compiler may take advantage of the array being two-dimensional and f.cols being the number of columns, comparison of indexes can be multidimensionally developed so as to facilitate an analysis. For instance, in this example, the problem can be replaced with the following,    an analysis of (cols*j+i)div cols    and (cols*j+2*i−1)div cols    an analysis of (cols*j+i)mod cols    and (cols*j+2*i−1)mod colsso it can easily be analyzed as having parallelism in the direction of j. However, costs for such modifications and extensions of specifications are very high. With respect to Java in particular, in consideration of the present circumstances where Java is spreading worldwide, it is not easy to effectively extend its specifications by addition of a new array object or by dependence on a specific library.
In addition, while a method to analyze an expression tree of an arithmetic expression without extending language specifications is also thinkable, it has a problem that an analysis becomes difficult when the expression tree is transformed due to deletion of a common subexpression and so on in addition to requirement of support to specify the dimensional.